package code;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class FindWhetherExistsPath_day15 {
    public static void main(String[] args) {
    int n=3;
    int[][] graph= {{0, 1},{0, 2},{0, 4},{0, 4},{0, 1},{1, 3},{1, 4},{1, 3},{2, 3},{3, 4}};
    int start=0;
    int end=4;
    boolean result = findWhetherExistsPath(n, graph, start, end);
    System.out.println(result);
    }

    public static boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        List<List<Integer>> list=new ArrayList<>();
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        for (int[] v : graph) {
            if (v[0] < n && v[1] < n) { // 防止越界
                list.get(v[0]).add(v[1]);
            }
        }

        deque.add(start);
        boolean[] visited = new boolean[n];
        while (!deque.isEmpty()){
            start=deque.pop();
            List<Integer> ends=list.get(start);
            for(int i=0;i<ends.size();i++){
                if(ends.get(i)==target){
                    return true;
                }
                else {
                    if(!visited[ends.get(i)]){
                        visited[ends.get(i)]=true;
                        deque.add(ends.get(i));
                    }
                }
            }
        }
        return false;
    }

    }
